package middle.arrays;

import java.util.Stack;

@FunctionalInterface
public interface SingleNonDuplicate {
    /**
     * You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.
     *
     * Return the single element that appears only once.
     *
     * Your solution must run in O(log n) time and O(1) space.
     *
     * @param nums
     * @return
     */
    int singleNonDuplicate(int[] nums);
}
class SingleNonDuplicateImpl1 implements SingleNonDuplicate{

    /**
     * 由于数组的结构是 n*2 + 1，n个元素出现两次，nums的长度必定为奇数次，二分查找，每次优先考虑元素数量为奇数的那一边
     * @param nums
     * @return
     */
    @Override
    public int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        int left = 0, right = n - 1;
        int mid;
        while(left < right){
            int half = (right - left) / 2;
            mid = left + half;
            if(half % 2 == 0){
                if(mid > 0 && nums[mid] == nums[mid - 1]){
                    right = mid - 2;
                }else if(mid < n && nums[mid] == nums[mid + 1]){
                    left = mid + 2;
                }else{
                    break;
                }
            }else {
                if(mid > 0 && nums[mid] == nums[mid - 1]){
                    left = mid + 2;
                }else if(mid < n && nums[mid] == nums[mid + 1]){
                    right = mid - 2;
                }else{
                    break;
                }
            }

        }
        mid = (left + right) / 2;
        return nums[mid];
    }
}
class SingleNonDuplicateImpl2 implements SingleNonDuplicate{
    static final int[] TEST_01 = new int[]{1,3,3,7,7,10,10,11,11};
    static final int[] TEST_02 = new int[]{1,1,2};
    static final int[] TEST_03 = new int[]{1,2,2};
    static final int[] TEST_04 = new int[]{1,1,2,3,3,4,4,8,8};
    static final int[][] TESTS = new int[][]{TEST_01,TEST_02,TEST_03,TEST_04};
    public static void main(String[] args) {
        for(int[] TEST : TESTS){
            int a = new SingleNonDuplicateImpl2().test(TEST);
            int b = new SingleNonDuplicateImpl2().singleNonDuplicate(TEST);
            System.out.println(a + " " +(a == b));

        }

    }
    @Override
    public int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        int left = 0, right = n - 1, mid = 0;
        while(left < right){
            int half = (right - left) / 2;
            mid = left + half;
            if(half % 2 == 1){
                // mid 两侧区间都为奇数
                if(mid == 0 || mid == n - 1){
                    break;
                }else if(nums[mid] == nums[mid - 1]){
                    left = mid + 1;
                }else if(nums[mid] == nums[mid + 1]){
                    right = mid - 1;
                }else{
                    break;
                }
            }else{
                // mid 两侧区间都为偶数
                if(mid == 0 || mid == n - 1){
                    break;
                }else if(nums[mid] == nums[mid - 1]){
                    right = mid;
                }else if(nums[mid] == nums[mid + 1]){
                    left = mid;
                }else{
                    break;
                }
            }

        }
        mid = (left + right) / 2;
        return nums[mid];
    }
    public int test(int[] nums){
        int x = 0;
        for (int i = 0; i < nums.length; i++) {
            x ^= nums[i];
        }
        return x;
    }
}